Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

题目大意：给定链表，翻转m->n之间的元素，空间复杂度O(1)，链表只可以遍历一次

题目难度：Medium

/**
 * Created by gzdaijie on 16/6/5
 * 找到m-1（p）和m（q）,采用头插法将m + 1 -> n之间的数插到q之间
 * 更新q和cnt, head始终指向第m个元素,head.next即等待头插的元素
 * 避免m == 1,为链表添加头h
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) return head;
        ListNode h = new ListNode(-1);
        ListNode p, q;
        int cnt = 1;

        q = h.next = head;
        p = h;
        // 找到第m和m-1个元素
        while (cnt < m) {
            p = head;
            q = head = head.next;
            cnt++;
        }
        // 将m+1->n元素依次头插到p,q之间
        while (cnt < n) {
            ListNode t = head.next;
            head.next =  head.next.next;
            t.next = q;
            q = p.next = t;
            cnt++;
        }
        return h.next;
    }
}